1. Field of the Invention
The present invention relates to an optical packet buffering device that uses optical circuits that have limited buffer capacity or data holding time, in order to guide a plurality of optical packets such that they are not overlapped toward one lightpath, and to the buffering method thereof.
2. Description of the Prior Art
With advances in optical communications technology able to transfer large amounts of information, in order to achieve even higher levels of throughput, optical technology is being introduced into not only the transmission paths but also into optical packet switching. Typically in optical packet switching, an optical packet transfer process is performed and an optical packet switch is used therein. The functions of such an optical packet switch can be divided into the five categories of: (1) label lookup, (2) switching, (3) buffer management, (4) buffering and (5) routing. Typically, an optical packet switch that implements functions (2) and (4) above optically is called an optical packet switch. This consists of optical switches and optical buffers, having broadband characteristics because the data is transferred while remaining as an optical signal.
In addition, by improving (3) buffer management above, it is possible to make further improvements to the throughput of an optical packet switch. Logic circuits based on electronic circuits had conventionally been used for this (3) buffer management. This is because practical optical logic circuits had not been available.
One of the objects of buffer management is to prevent the collision of optical packets. In an optical packet switching network, if a plurality of optical packets should arrive simultaneously at an optical packet switch, then the optical packets are stored in different positions of buffers to avoid collision. FIG. 1 shows a queue that represents the state of a buffer. For example, in the current Internet technology, packet transmission is done without performing priority control as shown in FIG. 1. The packets that arrive at the packet switch are stored in the buffer if space is available regardless of priority.
In addition, an optical packet switch does not use a semiconductor memory, which is often used in the buffer described above. Since an optical packet switch does not use semiconductor memory for buffering, a method of implementing optical buffer must be used as reported in the literature such as Document 1: K. Habara et al., “Development of a large-capacity photonic packet switch using wavelength routing techniques,” Technical Report of IEICE, SSE99-149, February 2000, and Document 2: David K. Hunter and Meow C. Chia and Ivan Andonovic, “Buffering in Optical Packet Switches,” IEEE/OSA Journal of Lightwave Technology, Vol. 16, No. 12, pp. 2081-2094, December 1998.
Previously known optical buffers have used a plurality of optical fibers of different lengths. These are optical delay elements with different delay times, so the optical packets are stored for the length of this delay time. A method of controlling the optical packets that are allocated to these optical delay lines to be able to avoid collision is known. At this time, it is not possible to extract an optical packet at an arbitrary time, so it is necessary to prevent the collision of optical packets at the time of output, and for this reason, some sort of buffer management technique must be used at the time of input to the optical buffer, thereby controlling the delay times,
In addition, as examples of the conventional optical packet switch architecture, we shall present N-input×N-output optical packet switches with configurations consisting of N 1-input×N-output buffer-less optical switches and N N-input×1-output buffers. The respective 1-input×N-output switches and N-input×1-output buffers are connected in a substantially lattice-type manner. In order to configure the above 1-input×N-output optical packet switches as N-input×N-output optical packet switches that exhibit adequate performance, it is also necessary to process a plurality of optical packets that arrive simultaneously in a sufficiently short period of time, and thus it is important to adopt a buffer management scheme requiring a small amount of computation.
The above optical packet switches are constituted using optical switches. Known optical switches that can be used in this application include: mechanical optical switches that use drive coils as shown in the schematic diagram in FIG. 3(a), optical switches that use optical semiconductor devices as shown in the block diagram in FIG. 3(b) and Mach-Zehnder type optical switches (not shown).
With the above 1-input×N-output buffer-less optical switches, it is possible to perform high-speed label lookup by means of an optical label lookup function as recited in Document 4: N. Wada, H. Harai, W. Chujo, and F. Kubota, “Photonic packet routing based on ultiwavelength label switching using fiber Bragg gratings,” ECOC 2000 Technical Digest (26th European Conference on Optical Communication), vol. 4 (No. 10.4.6), pp. 71-72, September 2000. As a result, N-input×N-output optical packet switches exhibit high node throughput. However, in order to avoid collision of optical packets and decrease the percentage discarded, a buffer is required, so an N-input×1-output buffer is connected to each output port of the N-input×N-output optical packet switches.
Here follows a more specific description of the buffer management method for processing variable-length packets. This method is already well known. For example, in Document 3: F. Callegati, “Optical buffers for variable length packets,” IEEE Communications Letters, vol. 4, pp. 292-294, September 2000, control is done by the following method with the addition of round-robin scheduling.
With the output buffer type N-input×N-output optical packet switch shown in FIG. 2, N N-input×1-output buffer and N 1-input×N-output switches are used. When the amount of data transmitted increases, t is possible for up to N optical packets to arrive simultaneously at the N-input×1-output buffer.
In order to prevent the collision (or overlap) of these optical packets, delay line buffers are used. In this case, in order to store all of the optical packets, the process of finding the delay of N optical packets must be performed within the period of time lmin equivalent to the minimum optical packet length. Specifically, the time permitted for processing one optical packet is lmin/N. If this time is made to be equivalent to the processing time for one optical packet when buffering is performed according to a simple round-robin scheme, then this indicates that the buffer management can be performed by means of round-robin scheduling.
FIG. 4(a) shows the structure of a 4-input×1-output optical buffer. In this case, N=4. An optical buffer made up of optical delay elements consists of B(=4) optical delay elements using fiber delay lines, N×(B+1) optical switches and a buffer management device (or buffer manager). The B fiber delay lines {d0, d1, d2, d3} have lengths of integral multiples of the unit length D of delay line, giving lengths of {0, D, 2D, 3D}. In addition, round-robin scheduling based on a clock signal in the buffer manager is repeated every period of time T. For this reason, the buffer manager receives the optical packet information at a point in time separated from the N×(B+1) optical switch by more than the period of time T, and must use this information to find the delay time required for each of the N optical packets during this predefined period of time T. Since it is necessary to process the sequentially arriving optical packets during the period of time T, the relation T≦lmin must be satisfied. For example, as shown in FIG. 4(a), four optical packets arrive and the buffer manager stores the optical packets A, B and C in the delay lines d0, d2 and d3 and discards optical packet D. This type of control is achieved by the use of the buffer manager driving the optical switch. FIG. 4(b) shows the positions of the optical packets, when viewed from the output port, immediately after optical packet A is switched to delay line d0. As shown in FIG. 4(c), optical packets A, B and C are provided as output without collision. In this example, optical packet B had arrived in the buffer prior to optical packet A, but the arriving optical packets are processed sequentially in a round-robin fashion, so they are output in the order shown in FIG. 4(c).
Here follows a detailed description of the behavior of the buffer manager according to the flowchart in FIG. 5. Table 1 presents the main parts of the program.
[Table 1]
TABLE 1ln: packet lengthtn (n=1, . . . , N): arrival gap timef : temporary variable for queue lengthT : periodD : unit length of the delay elementB : number of the delay elementsfor n = 1 to N dobeginif (f! = 0)begin                                                        Δ              n                        =                          ⌈                                                f                  -                                      t                    n                                                  D                            ⌉                                ;                                                          if            ⁢                                                  ⁢                          Δ              n                                <          B                       beginf = tn + ln + ΔnD;Packet n is given delay Δn;endelse Packet n is discarded;endendf = max(f − T, 0);
The buffer manager performs processing in order to avoid optical packet collisions both internally or upon output. Here, f is defined to be the amount of time from a predetermined start time to within the round-robin repeat time T until the time tf when all of the optical packets within the optical fibers have left the buffer. Hereinafter this f is called the buffer occupancy. Each period T, the buffer manager finds the delay time of the optical packets that have arrived at all ports. The delay times given to the optical packets arriving within the same period are found in the order port k=1, 2, . . . , N. Let us assume that an optical packet with an optical packet length lk arrives at port k at the time tk taking the time t0 to be the origin. The, delay time t to be given to the optical packet in order to avoid a collision is t=f−tk. Here, upon considering that the delay line buffer has a discrete time characteristic, one can see that the optical packets should be given the following time delay (F1 of FIG. 5).
                                          Δ            k                    ⁢          D                =                              D            ×                          Ceil              ⁡                              (                                                      f                    -                                          t                      k                                                        D                                )                                              =                      D            ×                          ⌈                                                f                  -                                      t                    k                                                  D                            ⌉                                                          [                  Equation          ⁢                                          ⁢          1                ]            
Here, the function Ceil(x) represents a function that gives the smallest integer that is no less than x. If Δk<B, then that packet is stored in the Δkth delay line (F2). Conversely, if Δk≧B, then that optical packet is discarded. In this manner, a portion of the optical packets is discarded and the remainder is stored, so it is necessary to update the buffer occupancy f accordingly. Thus, when an optical packet is stored (F4), f is updated as follows.f=tk+lk+ΔkD  [Equation 2]
Once the delay of the optical packets at all ports is found, excluding the discarded ports, the buffer occupancy f is updated to the new value of max((f−T),0), thus getting ready for the optical packet processing in the next round-robin period after a time of T.
When such an optical delay line buffer is used, the interval between the optical packet arriving at port k and the optical packet stored immediately previously, or namely the optical packet output at the time indicated by the f used at the time of finding the delay in the optical packet arriving at port k, is as follows.Θk=ΔkD+tk−f  [Equation 3]
Document 6 (H. Harai, N. Wada, F. Kubota, and W. Chujo, “Contention resolution using multi-stage fiber delay line buffer in a photonic packet switch,” Proceedings of IEEE ICC 2002) recites a method wherein delay line buffer units are disposed in a tree structure, and buffer managers are placed in each. Taking N to be the number of ports, this increases the processing speed by N1/2 times in comparison to the round robin processing described above, but a group of delay lines must be placed at each buffer unit so the increased size of the optical element is a problem. In addition, Document 5 (A. Prakash, S. Sharif, and A. Aziz, “An O(log2N) parallel algorithm for output queuing,” Proceedings of IEEE Infocom 2002.) recites a method of performing the process of storing packets, not in optical buffers but rather in semiconductor memory buffers, as parallel processing. This makes the scale of the managing device N times that when using the round-robin process, and the processing speed is log2 N times as fast.
The round-robin scheme described above proceeds sequentially, with data processing regarding buffering being performed in a predetermined port order, so in order to perform high-speed buffering, it is necessary to perform the data processing at high speed but thus the buffering speed is limited. In addition, when the same number of processor units as the number of lightpaths are provided in parallel as recited in Document 5 above, or when delay line buffer units are provided in a tree structure as recited in Document 6 above, even in a method wherein parallel processing is used, the maximum processing time per processor units increases rapidly as the number of input lightpaths increases.
The present invention has as its object to improve the speed of buffering performed during the parallel processing of data, and provide an optical packet buffering device that is able to avoid a rapid increase in the maximum processing time per arithmetic operator even if the number of inputs increases.